/*****************************************************************************/
/*                                                                           */
/*                                  matchpat.c                               */
/*                                                                           */
/*                       Unix shell like pattern matching                    */
/*                                                                           */
/*                                                                           */
/*                                                                           */
/* (C) 2002     Ullrich von Bassewitz                                        */
/*              Wacholderweg 14                                              */
/*              D-70597 Stuttgart                                            */
/* EMail:       uz@musoftware.de                                             */
/*                                                                           */
/*                                                                           */
/* This software is provided 'as-is', without any expressed or implied       */
/* warranty.  In no event will the authors be held liable for any damages    */
/* arising from the use of this software.                                    */
/*                                                                           */
/* Permission is granted to anyone to use this software for any purpose,     */
/* including commercial applications, and to alter it and redistribute it    */
/* freely, subject to the following restrictions:                            */
/*                                                                           */
/* 1. The origin of this software must not be misrepresented; you must not   */
/*    claim that you wrote the original software. If you use this software   */
/*    in a product, an acknowledgment in the product documentation would be  */
/*    appreciated but is not required.                                       */
/* 2. Altered source versions must be plainly marked as such, and must not   */
/*    be misrepresented as being the original software.                      */
/* 3. This notice may not be removed or altered from any source              */
/*    distribution.                                                          */
/*                                                                           */
/*****************************************************************************/

#include <string.h>

/* common */
#include "matchpat.h"

/*****************************************************************************/
/*                       Character bit set implementation                    */
/*****************************************************************************/

typedef unsigned char CharSet[32]; /* 256 bits */

/* Clear a character set */
#define CS_CLEAR(CS) memset(CS, 0, sizeof(CharSet))

/* Set all characters in the set */
#define CS_SETALL(CS) memset(CS, 0xFF, sizeof(CharSet))

/* Add one char to the set */
#define CS_ADD(CS, C) ((CS)[(C) >> 3] |= (0x01 << ((C)&0x07)))

/* Check if a character is a member of the set */
#define CS_CONTAINS(CS, C) ((CS)[(C) >> 3] & (0x01 << ((C)&0x07)))

/* Invert a character set */
#define CS_INVERT(CS)                                                                                                  \
  do {                                                                                                                 \
    unsigned I;                                                                                                        \
    for (I = 0; I < sizeof(CharSet); ++I) {                                                                            \
      CS[I] ^= 0xFF;                                                                                                   \
    }                                                                                                                  \
  } while (0)

/*****************************************************************************/
/*                                   Code                                    */
/*****************************************************************************/

/* Escape character */
#define ESCAPE_CHAR '\\'

/* Utility macro used in RecursiveMatch */
#define IncPattern()                                                                                                   \
  Pattern++;                                                                                                           \
  if (*Pattern == '\0') {                                                                                              \
    return 0;                                                                                                          \
  }

static int RealChar(const unsigned char *Pattern)
/* Return the next character from Pattern. If the next character is the
** escape character, skip it and return the following.
*/
{
  if (*Pattern == ESCAPE_CHAR) {
    Pattern++;
    return (*Pattern == '\0') ? -1 : *Pattern;
  } else {
    return *Pattern;
  }
}

static int RecursiveMatch(const unsigned char *Source, const unsigned char *Pattern)
/* A recursive pattern matcher */
{

  CharSet CS;

  while (1) {

    if (*Pattern == '\0') {

      /* Reached the end of Pattern, what about Source? */
      return (*Source == '\0') ? 1 : 0;

    } else if (*Pattern == '*') {

      if (*++Pattern == '\0') {
        /* A trailing '*' is always a match */
        return 1;
      }

      /* Check the rest of the string */
      while (*Source) {
        if (RecursiveMatch(Source++, Pattern)) {
          /* Match! */
          return 1;
        }
      }

      /* No match... */
      return 0;

    } else if (*Source == '\0') {

      /* End of Source reached, no match */
      return 0;

    } else {

      /* Check a single char. Build a set of all possible characters in
      ** CS, then check if the current char of Source is contained in
      ** there.
      */
      CS_CLEAR(CS); /* Clear the character set */

      if (*Pattern == '?') {

        /* All chars are allowed */
        CS_SETALL(CS);
        ++Pattern; /* Skip '?' */

      } else if (*Pattern == ESCAPE_CHAR) {

        /* Use the next char as is */
        IncPattern();
        CS_ADD(CS, *Pattern);
        ++Pattern; /* Skip the character */

      } else if (*Pattern == '[') {

        /* A set follows */
        int Invert = 0;
        IncPattern();
        if (*Pattern == '!') {
          IncPattern();
          Invert = 1;
        }
        while (*Pattern != ']') {

          int C1;
          if ((C1 = RealChar(Pattern)) == -1) {
            return 0;
          }
          IncPattern();
          if (*Pattern != '-') {
            CS_ADD(CS, C1);
          } else {
            int C2;
            unsigned char C;
            IncPattern();
            if ((C2 = RealChar(Pattern)) == -1) {
              return 0;
            }
            IncPattern();
            for (C = C1; C <= C2; C++) {
              CS_ADD(CS, C);
            }
          }
        }
        /* Skip ']' */
        ++Pattern;
        if (Invert) {
          /* Reverse all bits in the set */
          CS_INVERT(CS);
        }

      } else {

        /* Include the char in the charset, then skip it */
        CS_ADD(CS, *Pattern);
        ++Pattern;
      }

      if (!CS_CONTAINS(CS, *Source)) {
        /* No match */
        return 0;
      }
      ++Source;
    }
  }
}

int MatchPattern(const char *Source, const char *Pattern)
/* Match the string in Source against Pattern. Pattern may contain the
** wildcards '*', '?', '[abcd]' '[ab-d]', '[!abcd]', '[!ab-d]'. The
** function returns a value of zero if Source does not match Pattern,
** otherwise a non zero value is returned. If Pattern contains an invalid
** wildcard pattern (e.g. 'A[x'), the function returns zero.
*/
{
  /* Handle the trivial cases */
  if (Pattern == 0 || *Pattern == '\0') {
    return (Source == 0 || *Source == '\0');
  }

  /* Do the real thing */
  return RecursiveMatch((const unsigned char *)Source, (const unsigned char *)Pattern);
}
